/**
 * @desc 01背包问题 原始代码
 * @param {Number} w 背包的重量
 * @param {Array} weightArr 每个物品的重量
 * @param {Array} valArr 每个物品的价值
 * 参考：https://segmentfault.com/a/1190000012829866
 */
const readline = require('readline')
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
})
// wArr表示物品体积数组 valArr表示物品价值数组 w表示背包容量 k表示次数
let wArr = [], valArr = []
let w = 0
let k = -1
rl.on('line', function (data) {
  if (k < 0) {
    k = data.trim().split(' ')[0]
    w = data.trim().split(' ')[1]
  }
  else {
    wArr.push(parseInt(data.trim().split(' ')[0]))
    valArr.push(parseInt(data.trim().split(' ')[1]))
  }
  if (k == wArr.length) {
    backpack(w, wArr, valArr)
    return
  }
})
// backpack(w, wArr, valArr)
function backpack (w, weightArr, valArr) {
  // 物品数量，从0开始
  let n = weightArr.length - 1
  // 保存结果的二维数组
  let tmpArr = [[]]
  // 只有一个物品的情况
  for (let a = 0; a <= w; a++) {
    // 这个物品装不进去（边界情况）
    if (a < weightArr[0]) {
      tmpArr[0][a] = 0
    } else {  // 这个物品可以装进去（边界情况）
      tmpArr[0][a] = valArr[0]
    }
  }

  // 有好几个物品的情况
  // 循环背包容量
  for (let j = 0; j <= w; j++) {
    // 循环物品个数
    for (let i = 1; i <= n; i++) {
      // 创建新行
      if (!tmpArr[i]) tmpArr[i] = []
      // 最后一个装不进去，所以最大值为前i-1个的最大值
      if (j < weightArr[i]) {
        tmpArr[i][j] = tmpArr[i - 1][j]
      } else { // 最后一个能装进去，找装与不装的最大值
        tmpArr[i][j] = Math.max(tmpArr[i - 1][j], tmpArr[i - 1][j - weightArr[i]] + valArr[i])
      }
    }
  }
  console.log(tmpArr[n][w])
}